package com.majie.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 * 拷贝出个临时数组,用于对比
 * <p>
 * 分而治之的思想  D&C
 * <p>
 * 时间复杂度:O( nlogn )
 * <p>
 * 存在拷贝的过程,所以是空间换时间
 *
 * @author majie
 * @date 2018-05-07
 */
public class MergeSort1 {

    /**
     * 排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private static void mergeSort(int[] arr, int left, int right) {

        //临界条件
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        //分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        //合
        merge(arr, left, mid, right);
    }

    /**
     * 合并
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {

        int[] aux = Arrays.copyOfRange(arr, left, right + 1);

        // 初始化，i指向左半部分的起始索引位置left；j指向右半部分起始索引位置mid+1
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {

            //左边处理完处理右边的,右边处理完处理左边的
            if (i > mid) {
                arr[k] = aux[j - left];
                j++;
            } else if (j > right) {
                arr[k] = aux[i - left];
                i++;
            } else if (aux[i - left] < aux[j - left]) {
                arr[k] = aux[i - left];
                i++;
            } else {
                arr[k] = aux[j - left];
                j++;
            }
        }
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {10, 6, 8, 3, 6, 5, 9, 4, 3, 1};
        mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
